package nowcoder;

public class InverseParis {
	private static long count;
	
	public static void main(String... args) {
		int[] a = {364,637,341,406,747,995,234,971,571,219,993,407,416,366,315,301,601,650,
				418,355,460,505,360,965,516,648,727,667,465,849,455,181,486,149,588,233,144,
				174,557,67,746,550,474,162,268,142,463,221,882,576,604,739,288,569,256,936,275,401,497,
				82,935,983,583,523,697,478,147,795,380,973,958,115,773,870,259,655,446,863,735,784,3,671,
				433,630,425,930,64,266,235,187,284,665,874,80,45,848,38,811,267,575};
		
		System.out.println(InverseParis2(a));
	}

	public static int InversePairs(int[] array) {
		int count = 0;
		for(int i = 0; i < array.length - 1; i++) {
			for(int j =  i + 1; j < array.length; j++) {
				if(array[i] > array[j])
					count++;
			}
		}
		return count % 1000000007;
	}
	
	public static int InverseParis2(int[] array) {
		if(array == null || array.length == 0)
			return 0;
		divide(array, 0, array.length - 1);
		return (int)(count % 1000000007);
	}
	
	public static void divide(int[] array, int l, int r) {
		if(l >= r)
			return;
		int mid = (l + r) / 2;
		divide(array, l, mid);
		divide(array, mid + 1, r);
		merge(array, l, mid, r);
	}

	private static void merge(int[] array, int l, int mid, int r) {
		int[] tempArray = new int[r - l + 1];
		int lIndex = l;
		int rIndex = mid + 1;
		int index = 0;
		
		while(lIndex <= mid && rIndex <= r) {
			if(array[lIndex] > array[rIndex]) {
//				count += (mid - lIndex + 1);
				count = count % 1000000007 + ((mid - lIndex + 1)%1000000007);
				System.out.println(count);
				tempArray[index] = array[rIndex];
				rIndex++;
			}else {
				tempArray[index] = array[lIndex];
				lIndex++;
			}
			index++;
		}
		
		while(lIndex <= mid) {
			tempArray[index] = array[lIndex];
			lIndex++;
			index++;
		}
		
		while(rIndex <= r) {
			tempArray[index] = array[rIndex];
			rIndex++;
			index++;
		}
		
		for(int i = 0; i < tempArray.length; i++) {
			array[l + i] = tempArray[i];
		}
	}

}
